package com.swjd.tree;

import java.util.Arrays;

/**
 * 堆排序
 */
public class HeapSort {
    public static void main(String[] args) {
        int arr[] = {4, 6, 8, 5, 9};
/*        adiustHeap(arr,1,arr.length);
        System.out.println(Arrays.toString(arr));
        adiustHeap(arr,0,arr.length);
        System.out.println(Arrays.toString(arr));*/
        //      找出最后一个非叶子节点           向上循环
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adiustHeap(arr, i, arr.length);
            System.out.println(Arrays.toString(arr));//这里就得到大顶堆树了
        }

        int temp;
        for (int j = arr.length - 1; j > 0; j--) {
            //对大顶堆开始将堆顶元素与末尾元素交换
            temp = arr[j];
            arr[j] = arr[0]; //第一次交换时,arr[0]肯定是在大顶堆的堆顶，也就是最大值，arr[j]是在最后
            arr[0] = temp;
            adiustHeap(arr,0,j);
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 升序堆排序
     *
     * @param arr 需要排序的数组
     */
    public static void heapSort(int arr[]) {
        System.out.println("堆排序");
    }

    /**
     * 将以i为顶点的树转成大顶堆
     *
     * @param arr    需要转换的数组
     * @param i      非叶子节点在数组中的索引
     * @param lenght 需要调整的元素个数
     */
    public static void adiustHeap(int arr[], int i, int lenght) {
        //保存当前值
        int temp = arr[i];
        //开始转化 从i开始往下遍历左子节点
        for (int k = i * 2 + 1; k < lenght; k = k * 2 + 1) {
            if (k + 1 < lenght && arr[k] < arr[k + 1]) {
                //说明左子节点的值小于右子节点l
                k++;//让k指向右子节点
            }
            if (arr[k] > temp) {
                //如果子节点大于父节点
                arr[i] = arr[k];
                i = k;//让其从i开始继续比较 使i指向最大值 从最大值开始比较
            } else {
                break;//由于是从最后一个非叶子节点开始转换 所以可以直接退出，下面的已经转换排完了
            }
            arr[i] = temp;//由于arr[i]跟arr[k]交换位置，之前只把k放到i的位置上 之后把k的值给了i，所以现在把"i"的值再给k
        }
    }
}